1. Technical Field
The present invention relates in general to a method and system for data processing and in particular to a method and system for cache management within a data processing system. Still more particularly, the present invention relates to a method and system for handling a conflict between two operation requests in the cache of a data processing system.
2. Description of the Related Art
To maximize data processing system performance, the memory of a data processing system is typically arranged hierarchically, with one or more lower levels of memory, which may include nonvolatile storage and a main store, and one or more upper levels of memory, which typically include one or more levels of cache. As will be appreciated by those skilled in the art, cache memory is typically small relative to the main store and affords the processor(s) within the data processing system relatively rapid access to data and instructions.
Cache memories in conventional data processing systems are typically set associative, that is, the main store address of data is utilized to map the data to a particular congruence class that contains multiple entries or members in which the data can be stored. The data (including instructions) stored within the cache are recorded in a cache directory utilizing tags derived from the main store address, typically by selecting predetermined address bits. Thus, in response to receiving a request address, logic within the cache directory compares each of the tags stored in the directory set corresponding to the congruence class to which the request address maps with the tag bits of the request address in order to determine whether or not data associated with the request address resides in the cache. If the associated data resides in the cache, a "hit" occurs and the data is handled in accordance with the type of the request. On the other hand, if the data does not reside in the cache, a "miss" occurs. If, for example, a miss occurs in response to a processor's read request, the contents of an entry within the congruence class must be replaced with the requested data. In addition, if the contents of the replaced entry are modified with respect to the contents of the corresponding address in the main store, the modified data must be written to a lower level cache or to the main store. This replacement operation is known as a castout. Based upon the principle of locality of reference, the entry that is replaced is typically selected in accordance with a least recently used (LRU) algorithm that determines the least recently accessed entry within the congruence class.
In order to maintain data coherency and consistency, multiprocessor data processing systems typically employ either a directory-based or snoop-based communication protocol that notifies cache memories of data accesses occurring elsewhere within the data processing system. The caches utilize the data access information, which hereinafter will be referred to as snoop requests, to invalidate data, writeback data, update the coherency status of directory entries, or take other appropriate action based upon the coherency protocol implemented within the data processing system.
The present invention includes a recognition that a problem can arise when snoop requests received by a cache conflict with cache operation requests received from the cache's associated processor. For example, if a snoop request requires the cache to update a particular directory entry and a read request mapping to the same congruence class as the snoop request misses in the cache, it is possible that the congruence class entry selected for replacement by the replacement algorithm in response to the miss is associated with the directory entry that must be updated in response to the snoop request. In the prior art, a conflict between a castout operation and a snoop operation has been handled in one of two ways.
First, the cache can handle the conflict between the castout operation and the snoop operation simply by delaying servicing the processor's read request (and the concomitant castout operation) until the update required by the snoop request has been performed. A problem with this prior art approach is that the cache must reread the directory entry to obtain the updated coherency status of the directory entry prior to performing the castout operation. Rereading the cache directory to ascertain the updated coherency status not only slows processor performance by increasing data latency, but also consumes valuable directory access bandwidth. The identification of which congruence class entry is to be replaced by the castout operation can also be complicated by the fact that the LRU bits identifying the least recently used entry may have changed between receipt of the read request that prompted the castout operation and the completion of the cache operation initiated in response to the snoop request.
Second, a cache can handle a conflict between a castout operation and a snoop request by replacing a congruence class entry other than the LRU entry. While the second solution improves upon the first in that both the snoop request and the read request can be serviced without delay, the selection of an alternative "victim" for replacement can require a deep logic path including numerous levels of logic gates. Because of the delay inherent in propagating signals through such deep logic paths, it would be preferable to identify an alternative solution for caches within state-of-the-art data processing systems that utilize high clock frequencies.
As should thus be apparent, it would be desirable to provide an improved method and system for efficiently handling a conflict between a two operations requests in a cache of a data processing system.